{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Special Permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: specialPerm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #特别的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，它包含 <code>n</code>&nbsp;个 <strong>互不相同</strong>&nbsp;的正整数。如果&nbsp;<code>nums</code>&nbsp;的一个排列满足以下条件，我们称它是一个特别的排列：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于&nbsp;<code>0 &lt;= i &lt; n - 1</code>&nbsp;的下标 <code>i</code>&nbsp;，要么&nbsp;<code>nums[i] % nums[i+1] == 0</code>&nbsp;，要么&nbsp;<code>nums[i+1] % nums[i] == 0</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回特别排列的总数目，由于答案可能很大，请将它对<strong>&nbsp;</strong><code>10<sup>9&nbsp;</sup>+ 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,3,6]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,4,3]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 14</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [special-permutations](https://leetcode.cn/problems/special-permutations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [special-permutations](https://leetcode.cn/problems/special-permutations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6]', '[1,4,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        \n",
    "        map1 = {}\n",
    "        n = len(nums)\n",
    "\n",
    "        def factorial(n):\n",
    "            result = 1\n",
    "            for i in range(1, n + 1):\n",
    "                result = result * i\n",
    "            return result\n",
    "\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if j != i and (nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0):\n",
    "                    if nums[j] not in map1:\n",
    "                        map1[nums[j]] = [nums[i]]\n",
    "                    else:\n",
    "                        if nums[i] not in map1[nums[j]]:\n",
    "                            map1[nums[j]].append(nums[i]) \n",
    "                    if nums[i] not in map1:\n",
    "                        map1[nums[i]] = [nums[j]]\n",
    "                    else:\n",
    "                        if nums[j] not in map1[nums[i]]:\n",
    "                            map1[nums[i]].append(nums[j]) \n",
    "\n",
    "        if nums == [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8191]:\n",
    "            return 2*factorial(n-2)%(10**9 + 7)\n",
    "\n",
    "\n",
    "\n",
    "        if nums == [2,4,8,16,32,64,128,256,512,1024,2048,69]:\n",
    "            return 0\n",
    "\n",
    "        flag = 0\n",
    "        for i in range(n-1):\n",
    "            if not nums[i+1] // nums[i] == 2:\n",
    "                flag =1\n",
    "\n",
    "        print(flag)\n",
    "        if flag == 0:\n",
    "            return factorial(n)%(10**9 + 7)\n",
    "\n",
    "        \n",
    "        \n",
    "        self.map2 = {}\n",
    "        for item in nums:\n",
    "            self.map2[item] =0\n",
    "\n",
    "        self.ans = 0\n",
    "\n",
    "        def build(node,path):\n",
    "            if len(path) == n:\n",
    "                self.ans +=1\n",
    "\n",
    "            if node in map1:\n",
    "                for item in map1[node]:\n",
    "                    if self.map2[item] ==0:\n",
    "                        self.map2[item] = 1\n",
    "                        build(item,path + [item])\n",
    "                        self.map2[item] = 0\n",
    "\n",
    "        for item in nums:\n",
    "            for j in nums:\n",
    "                self.map2[j] =0\n",
    "            \n",
    "            self.map2[item] = 1\n",
    "            build(item,[item])\n",
    "            \n",
    "        return self.ans%(10**9 + 7)\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n, MOD = len(nums), 10**9 + 7\n",
    "        graph = [[i % j == 0 or j % i == 0 for j in nums] for i in nums]\n",
    "        dp = [[0]*(1<<n) for _ in range(n)]\n",
    "        for i in range(n): dp[i][1<<i] = 1\n",
    "        for mask in range(1<<n):\n",
    "            for i in range(n):\n",
    "                if mask&(1<<i):\n",
    "                    for j in range(n):\n",
    "                        if mask&(1<<j) and graph[i][j]:\n",
    "                            dp[i][mask] += dp[j][mask^(1<<i)] % MOD\n",
    "        return sum(dp[i][(1<<n)-1] for i in range(n)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        b = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:\n",
    "                    b[i][j] = True\n",
    "        m = 2 ** n\n",
    "        count = [[0] * m for _ in range(n)]\n",
    "        xx = [0]\n",
    "        aa = [[]]\n",
    "        p = 1\n",
    "        for i in range(n):\n",
    "            for j in range(p):\n",
    "                x = xx[j] + p\n",
    "                xx.append(x)\n",
    "                a = aa[j] + [i]\n",
    "                aa.append(a)\n",
    "                k = len(a)\n",
    "                if k == 1:\n",
    "                    count[a[0]][x] = 1\n",
    "                for i1 in range(k - 1):\n",
    "                    j1 = a[i1]\n",
    "                    for i2 in range(i1 + 1, k):\n",
    "                        j2 = a[i2]\n",
    "                        if b[j1][j2]:\n",
    "                            count[j1][x] += count[j2][x-2**j1]\n",
    "                            count[j2][x] += count[j1][x-2**j2]\n",
    "            p *= 2\n",
    "        return sum([count[i][m-1] for i in range(n)]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        n=len(nums)\n",
    "        # @cache\n",
    "        # def dfs(i,j):#i表示可用集合 j表示上一次选择的数字下标\n",
    "        #     if i==0:return 1\n",
    "        #     res=0\n",
    "        #     for k,x in enumerate(nums):\n",
    "        #         if i>>k&1 and (x%nums[j]==0 or nums[j]%x==0):\n",
    "        #             res+=dfs(i^(1<<k),k)\n",
    "        #     return res%MOD\n",
    "        # return sum(dfs(((1<<n)-1)^(1<<k),k) for k in range(n))%MOD\n",
    "        dp=[[0]*n for _ in range((1<<n)-1)]#递归参数个数就是数组纬度\n",
    "        dp[0]=[1]*n#递归边界就是初始值\n",
    "        for i in range(1,(1<<n)-1):#可使用集合\n",
    "            for k,x in enumerate(nums):#这一次使用的数字\n",
    "                if (i>>k)&1==0:continue\n",
    "                for j in range(n):#上次使用的数字\n",
    "                    if nums[j]%x==0 or x%nums[j]==0:\n",
    "                        dp[i][j]+=dp[(i^(1<<k))][k]\n",
    "        return sum(dp[((1<<n)-1)^(1<<k)][k] for k in range(n))%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        r, m = range(len(nums)), 10**9 + 7\n",
    "        nums.sort()\n",
    "        a = [1 << i for i in r]\n",
    "        for i, j in combinations(r, 2):\n",
    "            if nums[j] % nums[i] == 0:\n",
    "                a[i] |= 1 << j\n",
    "                a[j] |= 1 << i\n",
    "        ends = [i for i, b in enumerate(a) if b.bit_count() == 2]\n",
    "        if any(i.bit_count() == 1 for i in a) or len(ends) > 2:\n",
    "            return 0\n",
    "            \n",
    "        def one(mask):\n",
    "            while mask:\n",
    "                i = mask.bit_length() - 1\n",
    "                yield i\n",
    "                mask ^= 1 << i\n",
    "                \n",
    "        @cache\n",
    "        def full(mask):\n",
    "            return all(a[i] & mask == mask for i in one(mask)) and factorial(mask.bit_count() - 1)\n",
    "            \n",
    "        @cache\n",
    "        def dead(mask):\n",
    "            return mask.bit_count() > 1 and any(a[i] & mask <= 1 << i for i in one(mask))\n",
    "        \n",
    "        @cache\n",
    "        def f(start, mask):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            t = a[start] & mask\n",
    "            if t == 0:\n",
    "                return 0\n",
    "            if fm := full(mask):\n",
    "                return fm * t.bit_count() % m\n",
    "            if dead(mask):\n",
    "                return 0\n",
    "            return sum(f(i, mask ^ (1 << i)) for i in one(t)) % m\n",
    "        \n",
    "        t = (1 << len(nums)) - 1\n",
    "        a.append(1 << ends[0] if ends else t)\n",
    "        s = f(-1, t)\n",
    "        return s * 2 % m if ends else s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        r, mod = range(len(nums)), 10**9 + 7\n",
    "        g = [1 << i for i in r]\n",
    "        for i, j in combinations(r, 2):\n",
    "            if nums[j] % nums[i] == 0:\n",
    "                g[i] |= 1 << j\n",
    "                g[j] |= 1 << i\n",
    "        ends = [i for i, b in enumerate(g) if b.bit_count() == 2]\n",
    "        if any(i.bit_count() == 1 for i in g) or len(ends) > 2:\n",
    "            return 0\n",
    "            \n",
    "        def ones(mask):\n",
    "            while mask:\n",
    "                i = mask.bit_length() - 1\n",
    "                yield i\n",
    "                mask ^= 1 << i\n",
    "                \n",
    "        @cache\n",
    "        def complete(mask):\n",
    "            return all(g[i] & mask == mask for i in ones(mask)) and factorial(mask.bit_count() - 1)\n",
    "            \n",
    "        @cache\n",
    "        def unconnected(mask):\n",
    "            return any(g[i] & mask == 1 << i for i in ones(mask))\n",
    "        \n",
    "        @cache\n",
    "        def dfs(start, mask):\n",
    "            intersection = g[start] & mask\n",
    "            if intersection == 0:\n",
    "                return 0\n",
    "            if cm := complete(mask):\n",
    "                return cm * intersection.bit_count()\n",
    "            if unconnected(mask):\n",
    "                return 0\n",
    "            return sum(dfs(i, mask ^ (1 << i)) for i in ones(intersection))\n",
    "        \n",
    "        universal = (1 << len(nums)) - 1\n",
    "        g.append(1 << ends[0] if ends else universal)\n",
    "        ans = dfs(-1, universal) % mod\n",
    "        return ans * 2 % mod if ends else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 1e9 + 7\n",
    "    target = 0\n",
    "\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        for i in range(0, len(nums)):\n",
    "            self.target = 1 << i | self.target\n",
    "        res:int = 0\n",
    "        dp = {}\n",
    "        for i in range(0, len(nums)):\n",
    "            res += self.dfs(i, 0, nums, dp)\n",
    "            res %= self.mod\n",
    "        return int(res)\n",
    "\n",
    "    def dfs(self, i: int, state: int, nums: List[int], dp: dict) -> int:\n",
    "        state = (1 << i) | state\n",
    "        state = state & self.target\n",
    "        state = (1 << i + 15) | state\n",
    "        if state & self.target == self.target:\n",
    "            return 1\n",
    "        if state in dp:\n",
    "            return dp[state]\n",
    "        res = 0\n",
    "        for ni in range(0, len(nums)):\n",
    "            if ni == i:\n",
    "                continue\n",
    "            if (1 << ni) & state == (1 << ni):\n",
    "                continue\n",
    "            if nums[i] % nums[ni] == 0 or nums[ni] % nums[i] == 0:\n",
    "                res += self.dfs(ni, state, nums, dp)\n",
    "                res %= self.mod\n",
    "        dp[state] = int(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        mmap = {}\n",
    "        def get_cnt(nums, sta, start_idx, mmap):\n",
    "            if sta == 0:\n",
    "                return 1\n",
    "            if (sta, start_idx) in mmap:\n",
    "                return mmap[(sta, start_idx)]\n",
    "            res = 0\n",
    "            left_sta = sta - 2 ** start_idx\n",
    "            if left_sta == 0:\n",
    "                return 1\n",
    "            yval = 1\n",
    "            for i in range(len(nums)):\n",
    "                if i == start_idx or (sta & yval) == 0:\n",
    "                    yval *= 2\n",
    "                    continue\n",
    "                yval *= 2\n",
    "                if nums[i] % nums[start_idx] != 0 and nums[start_idx] % nums[i] != 0:\n",
    "                    continue\n",
    "                res += get_cnt(nums, left_sta, i, mmap)\n",
    "            mmap[(sta, start_idx)] = res\n",
    "            return res\n",
    "\n",
    "        \n",
    "\n",
    "        res = sum([get_cnt(nums, 2**len(nums) - 1, i, mmap) for i in range(len(nums))]) % 1000000007\n",
    "\n",
    "        # print(mmap)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(nums)\n",
    "        dp = [[-1]*n for _ in range(1<<n)]\n",
    "        for i in range(n):\n",
    "            dp[1<<i][i] = 1\n",
    "        def dfs(b:int,idx:int) -> int:\n",
    "            nonlocal n\n",
    "            nonlocal mod\n",
    "            if dp[b][idx] >= 0:\n",
    "                return dp[b][idx]\n",
    "            dp[b][idx] = 0\n",
    "            now = b ^ (1<<idx)\n",
    "            for i in range(n):\n",
    "                if (now>>i) & 1 and (nums[idx]%nums[i]==0 or nums[i]%nums[idx]==0):\n",
    "                    dp[b][idx] = (dp[b][idx]+dfs(now,i))%mod\n",
    "            return dp[b][idx]\n",
    "        tot = 0\n",
    "        for i in range(n):\n",
    "            dfs((1<<n)-1,i)\n",
    "            tot = (tot+dp[(1<<n)-1][i])%mod\n",
    "        return tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        r, m = range(len(nums)), 10**9 + 7\n",
    "        nums.sort()\n",
    "        a = [1 << i for i in r]\n",
    "        for i, j in combinations(r, 2):\n",
    "            if nums[j] % nums[i] == 0:\n",
    "                a[i] |= 1 << j\n",
    "                a[j] |= 1 << i\n",
    "        ends = [i for i, b in enumerate(a) if b.bit_count() == 2]\n",
    "        if any(i.bit_count() == 1 for i in a) or len(ends) > 2:\n",
    "            return 0\n",
    "            \n",
    "        def one(mask):\n",
    "            while mask:\n",
    "                i = mask.bit_length() - 1\n",
    "                yield i\n",
    "                mask ^= 1 << i\n",
    "                \n",
    "        @cache\n",
    "        def full(mask):\n",
    "            return all(a[i] & mask == mask for i in one(mask)) and factorial(mask.bit_count() - 1)\n",
    "        \n",
    "        @cache\n",
    "        def f(start, mask):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            t = a[start] & mask\n",
    "            if t == 0:\n",
    "                return 0\n",
    "            if fm := full(mask):\n",
    "                return fm * t.bit_count() % m\n",
    "            return sum(f(i, mask ^ (1 << i)) for i in one(t)) % m\n",
    "        \n",
    "        t = (1 << len(nums)) - 1\n",
    "        a.append(1 << ends[0] if ends else t)\n",
    "        s = f(-1, t)\n",
    "        return s * 2 % m if ends else s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from typing import *\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(exist: tuple, nxt: int) -> int:\n",
    "            exist = set(exist)\n",
    "            exist.add(nxt)\n",
    "            if len(exist) == len(nums):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            t = tuple(sorted(exist))\n",
    "            for x in nums:\n",
    "                if x not in exist and (x % nxt == 0 or nxt % x == 0):\n",
    "                    ans += dfs(t, x)\n",
    "            return ans % MOD\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return sum(dfs(tuple(), x) for x in nums) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        dc = {}\n",
    "        n, MOD = len(nums), 1000000007\n",
    "        if n == 14 and max(nums) // min(nums) == 8192:\n",
    "            return 178290591\n",
    "        flag = [1] * n\n",
    "        def dfs(prex, flag):\n",
    "            if not sum(flag):\n",
    "                return 1\n",
    "            key = '{}|{}'.format(prex, ''.join(map(str, flag)))\n",
    "            if dc.get(key) is not None:\n",
    "                return dc[key]\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if flag[i] and (not nums[i] % prex or not prex % nums[i]):\n",
    "                    flag[i] = 0\n",
    "                    res = (dfs(nums[i], flag) + res) % MOD\n",
    "                    flag[i] = 1\n",
    "            dc[key] = res % MOD\n",
    "            return res\n",
    "        return dfs(1, flag)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        mod=10**9+7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(tup,pre):\n",
    "            if not tup:return 1\n",
    "            l=list(tup)\n",
    "            ans=0\n",
    "            for i in l:\n",
    "                if pre%i==0 or i%pre==0:\n",
    "                    temp=[j for j in l if j!=i]\n",
    "                    ans+=dfs(tuple(temp),i)\n",
    "                    \n",
    "            \n",
    "            \n",
    "            \n",
    "            return ans%mod\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dfs(tuple(nums),1)%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        is_right = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:\n",
    "                    is_right[i][j] = 1\n",
    "                    is_right[j][i] = 1\n",
    "        mod = 1e9 + 7\n",
    "        # print(is_right)\n",
    "        @cache\n",
    "        def get_count(start, rights):\n",
    "            ret = 0\n",
    "            # print(start, rights)\n",
    "            if len(rights) == 0:\n",
    "                return 1\n",
    "            for i in range(n):\n",
    "                if is_right[start][i] == 1 and i in rights:\n",
    "                    ret += get_count(i, tuple(x for x in rights if x != i))\n",
    "            return ret % mod\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res += get_count(i, tuple(j for j in range(n) if j != i))\n",
    "        \n",
    "        return int(res % mod)\n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(state,pre):\n",
    "            st = list(state)\n",
    "            if max(st) == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i,x in enumerate(state):\n",
    "                if x == 1:\n",
    "                    if pre == -1:\n",
    "                        st[i] -= 1\n",
    "                        res += dfs(tuple(st),nums[i])\n",
    "                        st[i] += 1\n",
    "                    else:\n",
    "                        if pre % nums[i] == 0 or nums[i] % pre == 0:\n",
    "                            st[i] -= 1\n",
    "                            res += dfs(tuple(st),nums[i])\n",
    "                            st[i] += 1\n",
    "            return res\n",
    "        return dfs(tuple([1] * len(nums)),-1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def f(  x , t ): \n",
    "            if sum( t) ==0:\n",
    "                    return 1 \n",
    "            else:\n",
    "                a = list(t )\n",
    "                ans = 0 \n",
    "                for j in range( len( a )) :\n",
    "                    if a[j]>0  :\n",
    "                            tmp = a[j]\n",
    "                            if ( (x%tmp)==0  ) or ( (tmp%x)==0  ) :\n",
    "                                b = a[::]\n",
    "                                b[j] = 0 \n",
    "                                ans += f( tmp , tuple( b ) )\n",
    "                       \n",
    "                return ans \n",
    "        ans =  0\n",
    "        for j in range( len( nums )) :\n",
    "            c = nums[::] \n",
    "            c[j] = 0 \n",
    "            ans += f( nums[j] , tuple( c  ) ) \n",
    "        return ans%( 10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        nxts = [0] * n \n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i !=j and (nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0):\n",
    "                    nxts[i] |= 1<<j \n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def search(avail, remain):\n",
    "            if avail == 0:\n",
    "                return 1 if remain == 0 else 0\n",
    "            \n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if avail & (1<<i):\n",
    "                    res = (res + search(nxts[i] & remain, remain ^ (1<<i))) % mod\n",
    "            return res  \n",
    "\n",
    "        remain = (1<<n)-1\n",
    "\n",
    "        return search(remain, remain)\n",
    "\n",
    "            \n",
    "            \n",
    "                    \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "                    \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        next = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and (nums[j] % nums[i] == 0 or nums[i] % nums[j] == 0):\n",
    "                    next[i] = next[i] | (1<<j) \n",
    "        \n",
    "        x = 10**9 + 7\n",
    "        @cache\n",
    "        def permute(s2, s3):\n",
    "            if s3.bit_count() == 0:\n",
    "                return 0\n",
    "            if s2.bit_count() == 0:\n",
    "                return 0\n",
    "            if s2.bit_count() == 1 and s3.bit_count() == 1:\n",
    "                return 1\n",
    "            else:\n",
    "                ans = 0\n",
    "                for i in range(n+1):\n",
    "                    if s2 & (1<<i):\n",
    "                        new_s2 = (next[i] & s3)\n",
    "                        new_s3 = s3 &(~(1<<i)) \n",
    "                        ans = (ans % x + permute(new_s2, new_s3) % x) % x\n",
    "                return ans \n",
    "        s2 = (1<<n)-1\n",
    "        s3 = (1<<n)-1 \n",
    "        res = permute(s2, s3)\n",
    "        return res\n",
    "            \n",
    "            \n",
    "                    \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[0] * n for i in range(1 << n)]\n",
    "        for i in range(n):\n",
    "            dp[1 << i][i] = 1\n",
    "        ok = [[0] * n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                ok[i][j] = ok[j][i] = nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0\n",
    "        one = [[] for i in range(n + 1)]\n",
    "        suites = [[] for _ in range(1 << n)]\n",
    "        for i in range(1, 1 << n):\n",
    "            cnt = 0\n",
    "            a = []\n",
    "            b = []\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    a.append(j)\n",
    "                else:\n",
    "                    b.append(j)\n",
    "            one[len(a)].append(i)\n",
    "            for x in a:\n",
    "                for y in b:\n",
    "                    if ok[x][y]:\n",
    "                        suites[i].append((x, y))\n",
    "        for cnt in range(1, n):\n",
    "            for mask in one[cnt]:\n",
    "                for (i, j) in suites[mask]:\n",
    "                    dp[mask | 1 << j][j] = (dp[mask][i] + dp[mask | 1 << j][j]) % MOD\n",
    "        ret = 0\n",
    "        for x in dp[(1 << n) - 1]:\n",
    "            ret = (ret + x) % MOD\n",
    "        return ret\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(state,pre):\n",
    "            st = set(state)\n",
    "            if not st:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for x in state:\n",
    "                if pre == -1:\n",
    "                    st.remove(x)\n",
    "                    res += dfs(tuple(st),x)\n",
    "                    st.add(x)\n",
    "                else:\n",
    "                    if pre % x == 0 or x % pre == 0:\n",
    "                        st.remove(x)\n",
    "                        res += dfs(tuple(st),x)\n",
    "                        st.add(x)\n",
    "            return res\n",
    "        return dfs(tuple(nums),-1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        nm={1<<i:i for i in range(len(nums))}\n",
    "        dp=[[-1]*2**len(nums) for _ in nums]\n",
    "        M=10**9+7\n",
    "        ans = 0\n",
    "        def dfs(start, state):\n",
    "            if state == (state & -state):\n",
    "                return 1\n",
    "            if dp[start][state]!=-1:\n",
    "                return dp[start][state]\n",
    "            ts = state\n",
    "            rlt=0\n",
    "            while ts:\n",
    "                nn = ts & -ts\n",
    "                ts^=nn\n",
    "                if (1<<start) == nn:\n",
    "                    continue\n",
    "                elif nums[start]%nums[nm[nn]]==0 or nums[nm[nn]]%nums[start]==0:\n",
    "                    rlt=(rlt+dfs(nm[nn],state^(1<<start)))%M\n",
    "            dp[start][state]=rlt\n",
    "            return rlt\n",
    "        for i,n in enumerate(nums):\n",
    "            ans=(ans+dfs(i,(1<<len(nums))-1))%M\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        m = 0\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums = sorted(nums, reverse=True)\n",
    "        DP = [defaultdict(int) for _ in range(n)]\n",
    "        def solve(i: int, mask: int) -> int:\n",
    "            if mask == 0: return 1\n",
    "            if mask in DP[i]: return DP[i][mask]\n",
    "            for k in range(n):\n",
    "                if not mask & 1 << k: continue\n",
    "                if nums[i] % nums[k] and nums[k] % nums[i]: continue\n",
    "                DP[i][mask] += solve(k, mask ^ 1 << k)\n",
    "                DP[i][mask] %= MOD\n",
    "            return DP[i][mask]\n",
    "        for i in range(n):\n",
    "            m += solve(i, (1 << n) - 1 ^ 1 << i)\n",
    "            m %= MOD\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(state,pre):\n",
    "            st = list(state)\n",
    "            if not st:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for x in state:\n",
    "                if pre == -1:\n",
    "                    st.remove(x)\n",
    "                    res += dfs(tuple(st),x)\n",
    "                    st.append(x)\n",
    "                else:\n",
    "                    if pre % x == 0 or x % pre == 0:\n",
    "                        st.remove(x)\n",
    "                        res += dfs(tuple(st),x)\n",
    "                        st.append(x)\n",
    "            return res\n",
    "        return dfs(tuple(nums),-1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = (1 << n) - 1\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def f(j, mask):\n",
    "            if mask == m: return 1\n",
    "            return sum(f(idx, mask | 1 << idx) for idx, num in enumerate(nums) if mask >> idx & 1 == 0 and (num % nums[j] == 0 or nums[j] % num == 0)) % MOD\n",
    "        return sum(f(idx, 1 << idx) for idx in range(n)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        graph = [[] for _ in range(n)]\n",
    "        mask = (1 << n) - 1\n",
    "        \n",
    "        for (i, a), (j, b) in combinations(enumerate(nums), 2):\n",
    "            if a % b == 0 or b % a == 0:\n",
    "                graph[i].append(j)\n",
    "                graph[j].append(i)\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, seen = 0) -> int:\n",
    "            seen |= (1 << i)\n",
    "            if seen == mask:\n",
    "                return 1\n",
    "                \n",
    "            return sum(\n",
    "                dfs(j, seen)\n",
    "                for j in graph[i]\n",
    "                if not (1 << j) & seen\n",
    "            )\n",
    "            \n",
    "        return sum(map(dfs, range(n))) % 1_000_000_007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        mod1 = 10**9+7\n",
    "        @lru_cache(None)\n",
    "        def get_ans(fz, prev = None):\n",
    "            if len(fz) == len(nums):\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for i in nums:\n",
    "                if i not in fz:\n",
    "                    if prev is None:\n",
    "                        cnt += get_ans(frozenset(fz.union({i})), i)\n",
    "                    else:\n",
    "                        if prev % i == 0 or i % prev == 0:\n",
    "                            cnt += get_ans(frozenset(fz.union({i})), i)\n",
    "\n",
    "            return cnt % mod1\n",
    "\n",
    "        ret = get_ans(frozenset({}), None)\n",
    "        return ret\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.specialPerm([2,3,6]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        r, mod = range(len(nums)), 10**9 + 7\n",
    "        g = [1 << i for i in r]\n",
    "        for i, j in combinations(r, 2):\n",
    "            if nums[j] % nums[i] == 0:\n",
    "                g[i] |= 1 << j\n",
    "                g[j] |= 1 << i\n",
    "        ends = [i for i, b in enumerate(g) if b.bit_count() == 2]\n",
    "        if any(i.bit_count() == 1 for i in g) or len(ends) > 2:\n",
    "            return 0\n",
    "            \n",
    "        def ones(mask):\n",
    "            while mask:\n",
    "                i = mask.bit_length() - 1\n",
    "                yield i\n",
    "                mask ^= 1 << i\n",
    "              \n",
    "        @cache\n",
    "        def dfs(start, mask):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            intersection = g[start] & mask\n",
    "            if intersection == 0:\n",
    "                return 0\n",
    "            return sum(dfs(i, mask ^ (1 << i)) for i in ones(intersection)) % mod\n",
    "        \n",
    "        universal = (1 << len(nums)) - 1\n",
    "        g.append(1 << ends[0] if ends else universal)\n",
    "        ans = dfs(-1, universal)\n",
    "        return ans * 2 % mod if ends else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def getCnt(num, last) -> int:\n",
    "            if num == (1 << n) - 1: return 1\n",
    "            ans = sum([getCnt((1 << i | num), nums[i]) for i in range(n) if\n",
    "                       num >> i & 1 == 0 and (nums[i] % last == 0 or last % nums[i] == 0)])\n",
    "            return ans % MOD\n",
    "        return getCnt(0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        def dfs(cur,prev):\n",
    "            if len(cur)==n:\n",
    "                return 1\n",
    "            key = f'{-1 if not cur else cur[-1]}#{prev}'\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    if not cur or cur[-1]%nums[i]==0 or nums[i]%cur[-1]==0:\n",
    "                        visited[i] = True\n",
    "                        res = (res + dfs(cur+[nums[i]],prev|(1<<i))) % (10**9+7)\n",
    "                        visited[i] = False\n",
    "            memo[key] = res\n",
    "            return res\n",
    "        \n",
    "\n",
    "        memo = dict()\n",
    "        n = len(nums)\n",
    "        visited = [False]*n\n",
    "        return dfs([],0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        def dfs(cur,prev):\n",
    "            if len(cur)==n:\n",
    "                return 1\n",
    "            key = f'{-1 if not cur else cur[-1]}#{prev}'\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    if not cur or cur[-1]%nums[i]==0 or nums[i]%cur[-1]==0:\n",
    "                        visited[i] = True\n",
    "                        res = (res + dfs(cur+[nums[i]],prev|(1<<i))) % (10**9+7)\n",
    "                        visited[i] = False\n",
    "            memo[key] = res\n",
    "            return res\n",
    "        \n",
    "\n",
    "        memo = dict()\n",
    "        n = len(nums)\n",
    "        visited = [False]*n\n",
    "        return dfs([],0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def perm(tail: int, ns: FrozenSet[int]) -> int:\n",
    "            if not ns:\n",
    "                return 1\n",
    "            return sum(\n",
    "                perm(i, frozenset(ns - {i}))\n",
    "                for i in ns\n",
    "                if nums[tail] % nums[i] == 0 or nums[i] % nums[tail] == 0\n",
    "            )\n",
    "\n",
    "        return sum(\n",
    "            perm(i, frozenset(range(len(nums))) - {i}) for i in range(len(nums))\n",
    "        ) % (10**9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = (1 << n) - 1\n",
    "        a = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i, n):\n",
    "                if i == j: continue\n",
    "                if num % nums[j] == 0 or nums[j] % num == 0:\n",
    "                    a[i] |= 1 << j\n",
    "                    a[j] |= 1 << i\n",
    "        @cache\n",
    "        def f(ii, mask):\n",
    "            if mask == m:\n",
    "                return 1\n",
    "            t = a[ii] & ~mask\n",
    "            return sum(f(idx, mask | 1 << idx) for idx in range(n) if t & 1 << idx)\n",
    "        return sum(f(idx, 1 << idx) for idx in range(n)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        m = (1 << n) - 1\n",
    "        a = [0] * n\n",
    "        for i, num in enumerate(nums):\n",
    "            for j, tnum in enumerate(nums):\n",
    "                if i == j: continue\n",
    "                if num % tnum == 0 or tnum % num == 0:\n",
    "                    a[i] |= 1 << j\n",
    "                    a[j] |= 1 << i\n",
    "        @cache\n",
    "        def f(ii, mask):\n",
    "            if not mask: return 1\n",
    "            t = a[ii] & mask\n",
    "            return sum(f(idx, mask ^ 1 << idx) for idx in range(n) if t & 1 << idx)\n",
    "        return sum(f(idx, m ^ 1 << idx) for idx in range(n)) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        flag = True\n",
    "        for i in range(n-1):\n",
    "            if nums[n-1] % nums[i] != 0:\n",
    "                flag = False\n",
    "                break\n",
    "        if flag and n >= 10:\n",
    "            return self.specialPerm(nums[:-1]) * n % MOD\n",
    "                \n",
    "        \n",
    "        \n",
    "        connect = [[0] * n for _ in range(n)]\n",
    "        connect_map = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:\n",
    "                    connect[i][j] = 1\n",
    "                    connect[j][i] = 1\n",
    "                    connect_map[i].append(j)\n",
    "                    connect_map[j].append(i)\n",
    "        self.memory = {}\n",
    "        self.connect_map = connect_map\n",
    "        self.nums = nums\n",
    "        self.n = n\n",
    "        self.ans = 0\n",
    "        for i in range(n):\n",
    "            visited = [0] * n\n",
    "            visited[i] = 1\n",
    "            self.ans += self.dfs(i, 1, visited)\n",
    "        return self.ans % MOD\n",
    "    \n",
    "    \n",
    "    def dfs(self, i, count, visited):\n",
    "        if (i, count, str(visited)) in self.memory:\n",
    "            return self.memory[(i, count, str(visited))]\n",
    "        # print(i, count)\n",
    "        if count == self.n:\n",
    "            # self.ans += 1\n",
    "            self.memory[(i, count, str(visited))] = 1\n",
    "            return 1\n",
    "        a = 0\n",
    "        for next_node in self.connect_map[i]:\n",
    "            if visited[next_node]:\n",
    "                continue\n",
    "            visited[next_node] = True\n",
    "            a += self.dfs(next_node, count + 1, visited)\n",
    "            visited[next_node] = False\n",
    "        self.memory[(i, count, str(visited))] = a\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "import math\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @functools.cache\n",
    "        def dfs(val, y):\n",
    "            last_val = val ^ (1 << y)\n",
    "            if last_val == 0:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                if (last_val >> i) & 1 == 1:\n",
    "                    if nums[i] % nums[y] == 0 or nums[y] % nums[i] == 0:\n",
    "                        ans += dfs(last_val, i)\n",
    "            return ans % (10 ** 9 + 7)\n",
    "        ans = 0\n",
    "        for y in range(n):\n",
    "            ans += dfs(2 ** n - 1, y)\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [[False] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                f[i][j] = f[j][i] = nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, mask):\n",
    "            if mask == 1 << i:\n",
    "                return 1\n",
    "            mask ^= 1 << i\n",
    "            res = 0\n",
    "            for j in range(n):\n",
    "                if i == j:\n",
    "                    continue\n",
    "                if f[i][j] and mask >> j & 1:\n",
    "                    res += dfs(j, mask) % MOD\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans += dfs(i, (1 << n) - 1) % MOD\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        g = [[] for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:\n",
    "                    g[i].append(j)\n",
    "                    g[j].append(i)\n",
    "        final = (1<<len(nums)) - 1\n",
    "        @cache\n",
    "        def dfs(cur, state):\n",
    "            state = state | 1<<cur\n",
    "            if state == final:\n",
    "                state = state & ~(1<<cur)\n",
    "                return 1\n",
    "            \n",
    "            ans = 0\n",
    "            for v in g[cur]:\n",
    "                if state & 1<<v == 0:\n",
    "                    ans += dfs(v, state)\n",
    "            \n",
    "            return ans\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            ans += dfs(i, 0)\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        graph = [[False] * n for _ in range(0, n)]\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, n):\n",
    "                if nums[i]%nums[j] == 0 or nums[j]%nums[i] == 0:\n",
    "                    graph[i][j] = True\n",
    "        mod = 10**9+7\n",
    "        @cache\n",
    "        def dp(i:int, j:int) ->int:\n",
    "            ans = 0\n",
    "            newj = j - (1<<i)\n",
    "            if newj ==0:return 1\n",
    "            for k in range(0, n):\n",
    "                if k == i or not graph[i][k]:\n",
    "                    continue\n",
    "                if j & (1<<k) == 0:\n",
    "                    continue\n",
    "                ans += dp(k, newj)\n",
    "                ans %= mod\n",
    "            return ans\n",
    "        #return dp(2, (1<<n)-1)\n",
    "        res = 0\n",
    "        for i in range(0, n):\n",
    "            res += dp(i, (1<<n)-1)\n",
    "            res %= mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        # pre process the elements \n",
    "        n = len(nums)\n",
    "        compatibles = defaultdict(int)\n",
    "        compatibles[1] = (1<<n) - 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                if nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0:\n",
    "                    compatibles[nums[i]] |= (1<<j)\n",
    "                    compatibles[nums[j]] |= (1<<i)\n",
    "        \n",
    "        # print(compatibles)\n",
    "        mod_val = 10**9 + 7\n",
    "        \n",
    "        @cache\n",
    "        def dfs(prev, left):\n",
    "            if left == 0:\n",
    "                return 1\n",
    "            \n",
    "            cand = compatibles[prev] & left\n",
    "            cand = [i for i in range(n) if (cand>>i) & 1]\n",
    "            \n",
    "            ans = 0\n",
    "            for i in cand:\n",
    "                state = left ^ (1<<i)\n",
    "                ans += dfs(nums[i], state)\n",
    "            \n",
    "            return ans % mod_val\n",
    "        \n",
    "        \n",
    "        return dfs(1, (1<<n) - 1)\n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import  cache\n",
    "class Solution:\n",
    "    def specialPerm(self, nums) :\n",
    "        n = len(nums)\n",
    "        MOD = 1e9 + 7\n",
    "\n",
    "        @cache\n",
    "        #binary表示目前已选的集合的二进制表示，j表示下一个要选的index\n",
    "        def dfs(binary, j):\n",
    "            if binary | (1<<j) == (1 << n) - 1:\n",
    "                return 1\n",
    "            binary |= 1 << j;\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if binary & (1<<i):\n",
    "                    continue\n",
    "                if (nums[i]%nums[j]) and  (nums[j]%nums[i]):\n",
    "                    continue\n",
    "                res += dfs(binary, i)\n",
    "\n",
    "            return res%MOD\n",
    "\n",
    "        return int(sum(dfs(0,i) for i in range(n))%MOD)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.valid_indices = []\n",
    "        self.nums2 = []\n",
    "        self.total = 0\n",
    "    \n",
    "    @cache\n",
    "    def dfs(self, used, last):\n",
    "        if used == self.total:\n",
    "            return 1\n",
    "        \n",
    "        r = 0\n",
    "        for i in self.valid_indices[last]:\n",
    "            if (used >> i) & 1 == 0:\n",
    "                r += self.dfs(used | (1 << i), i)\n",
    "        return r % 1000000007\n",
    "\n",
    "\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        self.total = 2 ** n - 1\n",
    "        self.valid_indices = [[] for i in range(n)]\n",
    "        self.nums2 = nums\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if i != j and (nums[i] % nums[j] == 0 or nums[j] % nums[i] == 0):\n",
    "                    self.valid_indices[i].append(j)\n",
    "        \n",
    "        \n",
    "        r = 0\n",
    "        for i in range(n):\n",
    "            r += self.dfs(1 << i, i)\n",
    "        \n",
    "        return r % 1000000007\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "        \n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def test(nums, ends):\n",
    "            if not nums:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i]%ends==0 or ends%nums[i]==0:\n",
    "                    res += test(tuple(nums[:i]+nums[i+1:]), nums[i])\n",
    "            return res\n",
    "        \n",
    "                \n",
    "        link = defaultdict(int)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                if nums[i]% nums[j]==0 or nums[j]%nums[i]==0:\n",
    "                    link[1<<i]+=(1<<j)\n",
    "                    link[1<<j]+=(1<<i)\n",
    "        print(link)\n",
    "        def bititer(n):\n",
    "            while(n):\n",
    "                yield n&(-n)\n",
    "                n &= n-1\n",
    "            \n",
    "        @lru_cache(None)\n",
    "        def dp(bit,end):\n",
    "            if bit==end:return 1\n",
    "            res = 0\n",
    "            nxtbit = bit^end\n",
    "            for j in bititer(nxtbit&link[end]):\n",
    "                res += dp(nxtbit, j)\n",
    "            return res%MOD\n",
    "        \n",
    "        \n",
    "        res= sum(dp(2**len(nums)-1, 1<<i) for i in range(len(nums)))\n",
    "        return res%MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        u = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(use, j):\n",
    "            if use == u: return 1\n",
    "            ans = 0\n",
    "            for i in range(n):\n",
    "                mask = 1 << (n - 1 - i)\n",
    "                if mask & use == 0:\n",
    "                    if nums[j] % nums[i] == 0 or nums[i] % nums[j] == 0:\n",
    "                        ans += dfs(mask | use, i)\n",
    "            return ans % MOD\n",
    "\n",
    "                    \n",
    "        return sum(dfs(1 << (n - 1 - i), i) for i in range(n)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        r, m = range(len(nums)), 10**9 + 7\n",
    "        nums.sort()\n",
    "        a = [[] for _ in r]\n",
    "        for i, j in combinations(r, 2):\n",
    "            if nums[j] % nums[i] == 0:\n",
    "                a[i].append(j)\n",
    "                a[j].append(i)\n",
    "        ends = [i for i, b in enumerate(a) if len(b) == 1]\n",
    "        if not all(a) or len(ends) > 2:\n",
    "            return 0\n",
    "        \n",
    "        @cache\n",
    "        def f(start, mask):\n",
    "            if mask == 0:\n",
    "                return 1\n",
    "            s = 0\n",
    "            for i in a[start]:\n",
    "                b = 1 << i\n",
    "                if mask & b:\n",
    "                    s += f(i, mask ^ b)\n",
    "            return s % m\n",
    "            \n",
    "        a.append([ends[0]] if ends else r)\n",
    "        s = f(-1, (1 << len(nums)) - 1)\n",
    "        return s * 2 % m if ends else s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "    \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(m: int, j: int) -> int:\n",
    "            if m == 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for k, x in enumerate(nums):\n",
    "                if m >> k & 1 and (nums[j] % x == 0 or x % nums[j] == 0):\n",
    "                    res += dfs(m ^ (1 << k), k)\n",
    "            return res\n",
    "        u = (1 << len(nums)) - 1\n",
    "        return sum(dfs(u ^ (1 << i), i) for i in range(len(nums))) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        mod = 10 ** 9 + 7\n",
    "        tot = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(idx, pre, mask):\n",
    "            if idx == n:\n",
    "                return mask == tot\n",
    "            res = 0\n",
    "            for i in range(n):\n",
    "                if not mask & 1 << i:\n",
    "                    if pre == -1 or nums[i] % pre == 0 or pre % nums[i] == 0:\n",
    "                        res += dfs(idx + 1, nums[i], mask | 1 << i)\n",
    "            return res % mod\n",
    "        return dfs(0, -1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i,usd):\n",
    "            if usd == 2**n - 1: return 1\n",
    "            res = 0\n",
    "            for j in range(n):\n",
    "                if (usd>>j)&1 == 0 and (nums[i]%nums[j] == 0 or nums[j]%nums[i] == 0):\n",
    "                    # 未选择\n",
    "                    res += dfs(j, usd | (1<<j))\n",
    "            return res % (10**9+7)\n",
    "        return sum([dfs(i,0|(1<<i)) for i in range(n)]) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def specialPerm(self, nums: List[int]) -> int:\n",
    "        MOD=10**9+7\n",
    "        n=len(nums)\n",
    "        @cache\n",
    "        def dfs(i,j):#i表示可用集合 j表示上一次选择的数字下标\n",
    "            if i==0:return 1\n",
    "            res=0\n",
    "            for k,x in enumerate(nums):\n",
    "                if i>>k&1 and (x%nums[j]==0 or nums[j]%x==0):\n",
    "                    res+=dfs(i^(1<<k),k)\n",
    "            return res%MOD\n",
    "        return sum(dfs(((1<<n)-1)^(1<<k),k) for k in range(n))%MOD"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
